This invention relates to encryption and, more particularly, to voting arrangements that employ encryptions and decryptions.
The last few years have seen a large number of election schemes being proposed, introducing an array of attractive features, but often with an increasing degree of complexity in terms of computation and communication. There are two main approaches in proposed voting schemes. In the first, employing mix networks, votes are encrypted with the public key of a mix network, the encrypted votes are submitted to a distributed authority which decrypts the encrypted votes while it permutes them. Consequently, in the straight application of the mix network privacy is maintained as to who voted which way. In this approach robustness typically does not come easy, or at the price of lost privacy, because the talliers cannot prove that the correct computation was performed without revealing the permutation used. This is, of course, a major drawback in a setting where both privacy and correctness are paramount. It is easier to obtain robustness (without sacrificing privacy) for schemes of a second type, exemplified by the teachings of J. Cohen, M. Fischer, "A robust and verifiable cryptographically secure election scheme," FOCS '85, pp. 372-382; R. Cramer, R. Gennaro, B. Schoenmakers, "A Secure and Optimally Efficient Multi-Authority Election Scheme," Eurocrypt '97, pp. 103-118; R.
Cramer, M. Franklin, B. Schoenmakers, M. Yung, "Multi-Authority Secret-Ballot Elections with Linear Work," Eurocrypt '96, pp. 72-83; among others. These schemes, however, impose restrictions on the format of votes (typically limited to binary votes) and are more cumbersome to the voters, as they have to employ zero-knowledge proofs to prove that their votes are of a valid format.
Recently, an improved mix network has been disclosed in my copending application titled "Improved Mix Network," which was filed in the U.S. Patent Office on Jan. 13, 1998, and bearing the Ser. No. 09/005,920, U.S. Pat. No. 6,048,613.